package ACwing.P4Math.Prime;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Date : 2023-03-16
 * @Description:867. 分解质因数
 * 枚举到sqrt(n)
 */
public class PrimeFactorize {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        int x;
        while(n--!=0){
            x = Integer.parseInt(bufferedReader.readLine());
            divide(x);
        }

    }
    static void divide(int n){
        for (int i = 2; i <=n/i ; i++) {
            if(n%i==0){   //i一定是质数 比如 8=2x2x2,n中最多有一个大于sqrt(n)的质因子
                int s=0;
                while (n%i==0){
                    n/=i;
                    s++;
                }
                System.out.println(i+" "+s);
            }
        }
        if(n>1) System.out.println(n+" "+1);//最后剩下的一个质因子  比如 28=2x2x7
        System.out.println();
    }

}
